package wang.woran.sudoku;

import java.util.ArrayList;
import java.util.List;

/**
 * 穷举法（回溯法）
 */
public class Answer {
    private final int[][] rect = new int[][] { { 0, 1, 2, 9, 10, 11, 18, 19, 20 }, { 3, 4, 5, 12, 13, 14, 21, 22, 23 },
            { 6, 7, 8, 15, 16, 17, 24, 25, 26 }, { 27, 28, 29, 36, 37, 38, 45, 46, 47 },
            { 30, 31, 32, 39, 40, 41, 48, 49, 50 }, { 33, 34, 35, 42, 43, 44, 51, 52, 53 },
            { 54, 55, 56, 63, 64, 65, 72, 73, 74 }, { 57, 58, 59, 66, 67, 68, 75, 76, 77 },
            { 60, 61, 62, 69, 70, 71, 78, 79, 80 } };
    private int[] sudoku = new int[81];
    private int count = 0;

    private ProcessCallback callback;

    public interface ProcessCallback {
        void accept(int index, int value);
    }

    public void go(int[] sudoku, ProcessCallback callback) {
        try {

            this.callback = callback;
            this.sudoku = sudoku;
            tryy();
            // boolean result = tryOneCell(0);
            // System.out.println(result);
            printSudoku(sudoku);
            System.out.println(count);

        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    /**
     * 用循环的方式进行穷举
     */
    private void tryy() {
        //先把所有空格都记录下来，方便回溯
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 81; i++) {
            if (sudoku[i] == 0) {
                list.add(i);
            }
        }

        int i = 0;
        while (i > -1 && i < list.size()) {
            //用while循环是因为有时候需要i--，for循环不好处理
            count++;
            int index = list.get(i);
            if (sudoku[index] == 9) {
                sudoku[index] = 0;
                callback.accept(index, 0);
                i--;
                continue;
            }
            //j的初始值不是1，而是旧值+1，这样就兼容回溯的逻辑了
            int j = sudoku[index] + 1;
            while (j < 10) {
                //这里的while循环是因为循环完了要判断一下j==10，以便判断是否需要回溯，for循环还得用一个额外的变量
                sudoku[index] = j;
                if (check(sudoku)) {
                    callback.accept(index, j);
                    i++;
                    break;
                }
                j++;
            }
            if (j == 10) {
                //1-9都尝试过了，都会导致无解，所以i--，回溯
                sudoku[index] = 0;
                callback.accept(index, 0);
                i--;
            }
        }
        System.out.println("i:" + i);

    }

    /**
     * 递归的方式进行穷举
     */
    private boolean tryOneCell(int currentCell) throws Exception {
        if (sudoku[currentCell] != 0) {
            if (currentCell == 80) {
                return true;
            } else {
                return tryOneCell(currentCell + 1);
            }
        } else {
            for (int i = 1; i < 10; i++) {
                sudoku[currentCell] = i;
                // Thread.sleep(1);
                boolean result = check(sudoku);
                if (result) {
                    if (callback != null) {
                        callback.accept(currentCell, i);
                    }
                    count++;
                    if (currentCell == 80) {
                        return true;
                    } else {
                        result = tryOneCell(currentCell + 1);
                        if (result) {
                            // 如果后面的格子都找出来匹配的值了，那就返回了
                            // 如果后面return false了，那就说明有冲突了，那么当前的i就不适合当前的格子了，那就继续for循环
                            // 递归有点不好理解，可以尝试改成for循环
                            return true;
                        }
                    }
                }
            }
            sudoku[currentCell] = 0;
            if (callback != null) {
                callback.accept(currentCell, 0);
            }
            return false;
        }
    }

    public boolean check(int[] sudoku) {
        for (int i = 0; i < 9; i++) {
            boolean b = checkRect(sudoku, i);
            if (!b) {
                return false;
            }
            b = checkRow(sudoku, i);
            if (!b) {
                return false;
            }
            b = checkColumn(sudoku, i);
            if (!b) {
                return false;
            }
        }
        return true;
    }

    private boolean checkRow(int[] sudoku, int x) {
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            int curValue = sudoku[x * 9 + i];
            if (curValue != 0) {
                if (temp.contains(curValue)) {
                    return false;
                } else {
                    temp.add(curValue);
                }
            }
        }
        return true;
    }

    private boolean checkColumn(int[] sudoku, int y) {
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            int curValue = sudoku[i * 9 + y];
            if (curValue != 0) {
                if (temp.contains(curValue)) {
                    return false;
                } else {
                    temp.add(curValue);
                }
            }
        }
        return true;
    }

    private boolean checkRect(int[] sudoku, int index) {
        // 012
        // 345
        // 678
        List<Integer> temp = new ArrayList<>();
        int[] indexes = rect[index];
        for (int i = 0; i < 9; i++) {
            int curValue = sudoku[indexes[i]];
            if (curValue != 0) {
                if (temp.contains(curValue)) {
                    return false;
                } else {
                    temp.add(curValue);
                }
            }
        }
        return true;
    }

    public void printSudoku(int[] sudoku) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(sudoku[i * 9 + j]);
            }
            System.out.println();
        }
    }

}
